package leetcode.editor.cn.q1_300.q;

import java.util.ArrayList;
import java.util.List;

/**
 * @author qidi
 * @date 2021-12-06 15:08:41
 */
class Q0047_PermutationsIi {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> list = new ArrayList<>();
            process(nums, 0, list);
            return list;
        }

        private void process(int[] nums, int i, List<List<Integer>> list) {
            if (i == nums.length) {
                List<Integer> res = new ArrayList<>();
                for (int num : nums) res.add(num);
                list.add(res);
            }

            boolean[] visit = new boolean[21];

            for (int j = i; j < nums.length; j++) {
                if (!visit[nums[j] + 10]) {
                    visit[nums[j] + 10] = true;
                    swap(j, i, nums);
                    process(nums, i + 1, list);
                    swap(j, i, nums);
                }
            }
        }

        private void swap(int j, int i, int[] nums) {
            int tmp = nums[j];
            nums[j] = nums[i];
            nums[i] = tmp;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0047_PermutationsIi().new Solution();
        System.out.println(solution.permuteUnique(new int[]{1, 1, 2}));
    }
}